package com.itheima.arithmetic.linked;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;

/**
 * LRU算法思路: 维护一个有序的单向链表, 有序是指加入的时间, 头部就是最新的热点数据
 * 新加的节点来了: 去遍历链表 map + LinkedList 数据结合(查询和修改都是O(1))
 *  if(找到了){
 *    // 删除当前节点
 *    deleteCurrentNode();
 *
 *    // 把新的节点加入到链表头部
 *    insertNewNodeToHead();
 *  } else { // 没找到, 是否内存空间足够
 *
 *      if(内存空间不足) {
 *        //删除最后一个节点
 *        deleteTail();
 *      }
 *       // 新的节点直接加到链表头部
 *      insertNewNodeToHead();
 *  }
 */
public class LruCache<K, V> {

    /**
     * 缓存中存储元素的数量
     */
    private int size;

    /**
     * 最大元素数量
     */
    private int maxSize = 16;

    /**
     * 通过与链表配合，使其查找速度在O(1)下完成
     * 因为hash表的查询速度最快
     */
    private Map<K, Node<K, V>> map;
    /**
     * 链表优点：便于添加和删除元素，都在O(1)时间内完成
     */
    private LinkedList<Node<K, V>> linkedList;

    public LruCache(){
        this(16);
    }

    public LruCache(int size){
        if (size <= 0) {
            this.size = maxSize;
        } else {
            this.size = size;
        }
        map = new HashMap<>(this.size);
        linkedList = new LinkedList<>();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for(Node<K,V> node : linkedList ){
            stringBuilder.append(node.toString()).append(",");
        }
        return stringBuilder.toString().substring(0,stringBuilder.length()-1);
    }

    /**
     * 判断缓存元素是否存在，如果存在，则把链表中的元素删除，map中的数据不用删除，再在链表头部插入元素，并更新map
     * 当缓存没有满的话，直接把元素插入链表的表头，否则移除表尾元素（最旧未访问元素）, 再插入表头，注意更新map
     */
    public synchronized void put(K key, V value){
        Node<K, V> node = map.get(key);
        if (node != null) { // 存在
            linkedList.remove(node);
        } else { // 不存在

            // 要加入的节点
            node = new Node<>(key, value);

            // 缓存已满, 删除链表尾部, 再插入到表头
            if (size == map.size()) {
                linkedList.removeLast();
            }
        }

        // 直接加在链表头部
        linkedList.addFirst(node);

        // 更新map
        map.put(key, node);
    }
    /**
     * 如果key对应的数据存在，则返回相应value值，
     * 删除当前节点并把当前节点移到链表头部
     */
    public synchronized V get(K key){
        Node<K, V> node = map.get(key);
        if (Objects.isNull(node)) {
            return null;
        }

        // 删除当前节点并把当前节点移到链表头部
        linkedList.remove(node);
        linkedList.addFirst(node);
        return node.value;
    }

    /**
     * 根据key删除缓存元素
     */
    public void delete(K key){
        Node<K, V> node = map.get(key);
        if (Objects.nonNull(node)) {
            map.remove(key);
            linkedList.remove(node);
        }
    }

    private static class Node<K, V> {
        /**
         * 键
         */
        private K key;

        /**
         * 值
         */
        private V value;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }
        @Override
        public String toString() {
            return "(" +
                    "key=" + key +
                    ", value=" + value +
                    ')';
        }
    }

    public static void main(String[] args) {
        LruCache<String,String> lruCache = new LruCache<>(3);
        lruCache.put("one","one");
        lruCache.put("two","two");
        lruCache.put("three","three");
        System.out.println(lruCache.toString());
        lruCache.get("one");

        System.out.println(lruCache.toString());
        lruCache.put("four","four");
        System.out.println(lruCache.toString());

        lruCache.get("one");
        System.out.println(lruCache.toString());
        System.out.println(lruCache.get("five"));
        lruCache.put("four","five");
        System.out.println(lruCache.toString());
    }
}
